﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    class Point
    {
        public double x { get; private set; }
        public double y { get; private set; }
        public string Id { get; private set; }
        public Point(string id, double x, double y)
        {
            Id = id;
            this.x = x;
            this.y = y;
        }

        public override string ToString()
        {
            return string.Format("{2}({0:F1}, {1:F1})", x, y, Id);
        }
    }

    class ConvertHull
    {
        public static int ccw(Point a, Point b, Point c)
        {
            double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
            if (area2 < 0) return -1; // clockwise
            else if (area2 > 0) return +1; // counter-clockwise
            else return 0; // collinear
        }
        // isLeft(): tests if a point is Left|On|Right of an infinite line.
        //    Input:  three points P0, P1, and P2
        //    Return: >0 for P2 left of the line through P0 and P1
        //            =0 for P2 on the line
        //            <0 for P2 right of the line
        int IsLeft(Point P0, Point P1, Point P2)
        {
            return ccw(P0, P1, P2);
        }

        public void Run()
        {
            Point[] points = new Point[]{
                new Point("A", 6.0, 8.0),
                new Point("B", 3.0, 3.0),
                new Point("C", 4.0, 1.0),
                new Point("D", 0.0, 7.0),
                new Point("E", 5.0, 5.0),
                new Point("F", 1.0, 0.0),
                new Point("G", 7.0, 6.0),
                new Point("H", 8.0, 2.0),
                new Point("I", 9.0, 4.0),
                new Point("J", 2.0, 9.0)
            };

            foreach (Point p in points)
            {
                Console.WriteLine(p);
            }
            Console.WriteLine("\r\n***********************");

            // Point2D[] output = new Point2D[p.Length];

            Point[] output = bruteForceConvexHull(points);
            List<string> list = new List<string>();
            for (int i = 0; i < output.Length; ++i)
            {
                if (output[i] != null)
                {
                    Console.WriteLine(output[i]);
                    list.Add(output[i].Id);
                }
            }

            Console.WriteLine("\r\n----------------");
            foreach (Point p in points.OrderBy(e => e.y))
            {
                if (!list.Contains(p.Id))
                {
                    Console.Write(p.Id + " ");
                }
            }
        }

        public static Point[] bruteForceConvexHull(Point[] inputpointset)
        {
            Point[] result = new Point[inputpointset.Length];

            // first search for the point with minimum y value and start there. 
            //   p1, p2;
            Point startpoint = inputpointset[0];
            int i;
            for (i = 1; i < inputpointset.Length; i++)
            {
                if (startpoint.y > inputpointset[i].y)
                    startpoint = inputpointset[i];
            }
            result[0] = startpoint;

            // now start a loop, searching for the next vertex after the first one. 
            // in this code, we always search in the clockwise direction.
            int currentvertexindex = 0;
            Point currentvertex = result[currentvertexindex];
            Point pointtocheck = null;
            bool done;
            if (inputpointset.Length == 1) done = true;
            else done = false;
            while (!done)
            {
                // loop through each point to see if it is the next vertex
                for (i = 0; i < inputpointset.Length; i++)
                {
                    pointtocheck = inputpointset[i];
                    // can't test equal points because they don't form a line.
                    if (pointtocheck != currentvertex)
                    {
                        // check to see if all points are on right side of line 
                        //   from currentvertex to pointtocheck.
                        if (AllPointsOnRight(currentvertex, pointtocheck, inputpointset))
                        {
                            // pointtocheck is a vertex of polygon; break out. 
                            break;
                        }
                    }
                }
                // at this point, we should have found a vertex. 
                // if i== inputpointset.Length at this point, we didn't find a vertex, but that
                // should never happen!

                // if the found vertex is the same as the first vertex, we have finished. 
                // otherwise, add in the vertex and continue the loop.
                if (pointtocheck == result[0])
                {
                    done = true;
                }
                else
                {
                    // add a new vertex, get ready for next loop iteration.
                    currentvertexindex++;
                    result[currentvertexindex] = pointtocheck;
                    currentvertex = pointtocheck;
                }
            }

            return result;
        }


        // Takes input points p1 and p2, array of points A. 
        // consider the line from p1 to p2. 
        // if all points in A are on the line from p1 to p2 or to the right 
        // of the line (The "right" side of the line is the one where
        // you are assumed to be at p1 looking towards p2)   
        public static bool AllPointsOnRight(Point p1, Point p2, Point[] A)
        {
            // check all points to see if they are all on the right. 
            // use the properties of the determinant. 
            for (int i = 0; i < A.Length; i++)
            {
                if (determinantformula(p1, p2, A[i]) > 0)
                    return false;
            }

            return true;
        }

        // for input points p1 = (x1,y1), p2 = (x2,y2), p3 = (x3,y3), computes the determinant 
        //  | x1 y1 1 |
        //  | x2 y2 1 |
        //  | x3 y3 1 |
        // This determinant is positive when point p3 is to the left of the line
        //  from p1 to p2, and negative when point p3 is to the right of the line
        // Furthermore, the magnitude of this determinant is the twice the area 
        //  of the enclosed triangle.
        public static double determinantformula(Point p1, Point p2, Point p3)
        {
            return (p1.x * p2.y + p3.x * p1.y + p2.x * p3.y
                  - p3.x * p2.y - p2.x * p1.y - p1.x * p3.y);
        }

        int chainHull_2D(Point[] P, int n, Point[] H)
        {
            // the output array H[] will be used as the stack
            int bot = 0, top = (-1);  // indices for bottom and top of the stack
            int i;                // array scan index

            // Get the indices of points with min x-coord and min|max y-coord
            int minmin = 0, minmax;
            double ymin = P[0].y;
            for (i = 1; i < n; i++)
            {
                if (P[i].y != ymin) break;
            }
            minmax = i - 1;
            if (minmax == n - 1)
            {       // degenerate case: all x-coords == xmin
                H[++top] = P[minmin];
                if (P[minmax].y != P[minmin].y) // a nontrivial segment
                {
                    H[++top] = P[minmax];
                }
                H[++top] = P[minmin];           // add polygon endpoint
                return top + 1;
            }

            // Get the indices of points with max x-coord and min|max y-coord
            int maxmin, maxmax = n - 1;
            double xmax = P[n - 1].x;
            for (i = n - 2; i >= 0; i--)
            {
                if (P[i].x != xmax)
                {
                    break;
                }
            }
            maxmin = i + 1;

            // Compute the lower hull on the stack H
            H[++top] = P[minmin];      // push minmin point onto stack
            i = minmax;
            while (++i <= maxmin)
            {
                // the lower line joins P[minmin] with P[maxmin]
                if (IsLeft(P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
                    continue;          // ignore P[i] above or on the lower line

                while (top > 0)        // there are at least 2 points on the stack
                {
                    // test if P[i] is left of the line at the stack top
                    if (IsLeft(H[top - 1], H[top], P[i]) > 0)
                    {
                        break;         // P[i] is a new hull vertex
                    }
                    else
                    {
                        top--;         // pop top point off stack
                    }
                }
                H[++top] = P[i];       // push P[i] onto stack
            }

            // Next, compute the upper hull on the stack H above the bottom hull
            if (maxmax != maxmin)      // if distinct xmax points
            {
                H[++top] = P[maxmax];  // push maxmax point onto stack
            }
            bot = top;                 // the bottom point of the upper hull stack
            i = maxmin;
            while (--i >= minmax)
            {
                // the upper line joins P[maxmax] with P[minmax]
                if (IsLeft(P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
                    continue;          // ignore P[i] below or on the upper line

                while (top > bot)    // at least 2 points on the upper stack
                {
                    // test if P[i] is left of the line at the stack top
                    if (IsLeft(H[top - 1], H[top], P[i]) > 0)
                        break;         // P[i] is a new hull vertex
                    else
                        top--;         // pop top point off stack
                }
                H[++top] = P[i];       // push P[i] onto stack
            }

            if (minmax != minmin)
            {
                H[++top] = P[minmin];  // push joining endpoint onto stack
            }
            return top + 1;
        }
    }
}
